package 二叉树;

import java.util.Stack;

/**
 * 938. Range Sum of BST
 * https://leetcode.com/problems/range-sum-of-bst/
 *
 * Given the root node of a binary search tree(二叉搜索树),
 * return the sum of values of all nodes with value between L and R (inclusive).
 *
 * The binary search tree is guaranteed to have unique(唯一) values.
 *
 * Example 1:
 *
 * Input: root = [10,5,15,3,7,null,18], L = 7, R = 15
 * Output: 32
 *
 * Example 2:
 *
 * Input: root = [10,5,15,3,7,13,18,1,null,6], L = 6, R = 10
 * Output: 23
 *
 * Note:
 *
 * 1.The number of nodes in the tree is at most 10000.
 * 2.The final answer is guaranteed to be less than 2^31.
 *
 */
public class E_938_二叉搜索树的范围和 {

    /**
     * 深度优先检索
     * 递归解决 数在 L<NUM<R 之间的值和
     */
    public static int rangeSumBST(TreeNode root, int L, int R) {
        if (root == null) { return 0; }

        if (root.val > R) {
            return rangeSumBST(root.left, L, R);
        } else if (root.val < L) {
            return rangeSumBST(root.right, L, R);
        } else {
            return root.val + rangeSumBST(root.left, L, R) + rangeSumBST(root.right, L, R);
        }
    }

    /**
     * 深度优先检索
     * 迭代解决
     */
    public static int rangeSumBST2(TreeNode root, int L, int R) {
        if (root == null) { return 0; }

        int ans = 0;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();

            if (node.val > R) {
                stack.push(node.left);
            } else if (node.val < L) {
                stack.push(node.right);
            } else {
                ans += node.val;
            }
        }

        return ans;
    }


    public static void main(String[] args) {

    }
}
